package LeetCode.interview;

import util.LogUtils;

/*
 * 
 原题
　　Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. 
　　Do not allocate extra space for another array, you must do this in place with constant memory. 
For example, 
　　Given input array nums = [1,1,2], 
　　Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter 　　what you leave beyond the new length. 
题目大意
　　给定一个排序的数组，将数组中的重复元素去掉，相同的只保留一个，并且返回数组新的元素个数，不要创建一个新的数组来保存结果。在常量时间内解决这个问题 
解题思路
 	我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。
 	具体来说，用两个指针，快指针(i)指向当前数组遍历到的位置，慢指针(end)指向不重复序列下一个存放的位置，
 	这样我们一旦遍历到一个不重复的元素，就把它复制到不重复序列的末尾。判断重复的方法是记录上一个遍历到的数字，看是否一样。
 * @Date 2017-09-12 18：16
 */
public class _026_Remove_Duplicates_from_Sorted {
    public int removeDuplicates(int[] nums) {
    	if (nums==null || nums.length==0)	return 0;
    	int pre = nums[0];				//pre..之前一个元素
    	int end = 1;
    	int i;							
    	
    	for (i = 1; i < nums.length; i ++) {
    		if (nums[i] != pre) {				//新的元素 
    			nums[end] = nums[i];			//将新元素放到已经排好的旧元素的下一位
    			end++;
    			pre = nums[i];
    		}
    	}

        return end;								//end的索引位置，就是数组中去重后元素的个数
    }

	public static void main(String[] args) {
		LogUtils.println("结果", new _026_Remove_Duplicates_from_Sorted().removeDuplicates(new int[] {1, 2, 2, 4, 4, 5}));
	}
}
